---
title: STL 算法
---

C++ 标准模板库 (STL) 提供了一组丰富的通用算法，这些算法作用于元素范围。这些算法旨在高效且通过迭代器与各种容器类型配合使用。它们提供了强大的排序、搜索、转换和数据操作功能，通常比手动实现提供更优化的解决方案。本模块将这些算法与常见的 JavaScript 数组方法进行比较。

## 算法库概述

STL 算法通常位于 `<algorithm>` 标头中。它们是通用的，这意味着它们可以与不同的数据类型和容器类型配合使用，只要提供的迭代器符合算法的要求即可。算法与容器的分离是 STL 的一个关键设计原则，促进了可重用性和灵活性。

## 排序算法

排序算法以特定顺序排列元素。

### `std::sort`

*   默认情况下，以升序排序范围内的元素。
*   通常使用内省排序 (快速排序、堆排序和插入排序的混合) 实现平均 O(N log N) 的复杂度。

<UniversalEditor title="排序比较" compare={true}>
```javascript !! js
// JavaScript: Array.prototype.sort()
let numbers = [5, 2, 8, 1, 9];
numbers.sort((a, b) => a - b); // 升序排序
console.log(numbers); // [1, 2, 5, 8, 9]

let words = ["banana", "apple", "cherry"];
words.sort(); // 字典序排序
console.log(words); // ["apple", "banana", "cherry"]
```

```cpp !! cpp
// C++: std::sort
#include <iostream>
#include <vector>
#include <algorithm> // For std::sort
#include <string>

int main() {
  std::vector<int> numbers = {5, 2, 8, 1, 9};
  std::sort(numbers.begin(), numbers.end()); // 升序排序
  // for (int n : numbers) { std::cout << n << " "; }
  // std::cout << std::endl; // 输出: 1 2 5 8 9

  std::vector<std::string> words = {"banana", "apple", "cherry"};
  std::sort(words.begin(), words.end()); // 字典序排序
  // for (const std::string& w : words) { std::cout << w << " "; }
  // std::cout << std::endl; // 输出: apple banana cherry

  return 0;
}
```
</UniversalEditor>

### `std::stable_sort`

*   在排序元素的同时，保留等效元素的相对顺序。
*   通常使用合并排序或类似算法，复杂度为 O(N log N)。

### `std::partial_sort`

*   仅排序范围的一部分，特别是前 `n` 个元素。

## 搜索算法

搜索算法在范围内寻找元素。

### `std::find`

*   搜索值的第一次出现。
*   返回指向第一个匹配元素的迭代器，如果未找到则返回 `last`。
*   线性搜索，O(N) 复杂度。

<UniversalEditor title="搜索比较" compare={true}>
```javascript !! js
// JavaScript: Array.prototype.includes(), Array.prototype.indexOf()
let data = [10, 20, 30, 40, 50];

console.log(data.includes(30)); // true
console.log(data.includes(100)); // false

console.log(data.indexOf(20)); // 1
console.log(data.indexOf(99)); // -1
```

```cpp !! cpp
// C++: std::find
#include <iostream>
#include <vector>
#include <algorithm> // For std::find

int main() {
  std::vector<int> data = {10, 20, 30, 40, 50};

  auto it = std::find(data.begin(), data.end(), 30);
  // if (it != data.end()) {
  //   std::cout << "Found 30 at index: " << std::distance(data.begin(), it) << std::endl;
  // } else {
  //   std::cout << "30 not found." << std::endl;
  // }

  it = std::find(data.begin(), data.end(), 100);
  // if (it != data.end()) {
  //   std::cout << "Found 100." << std::endl;
  // } else {
  //   std::cout << "100 not found." << std::endl;
  // }

  return 0;
}
```
</UniversalEditor>

### `std::binary_search`

*   检查**已排序**范围中是否存在元素。
*   如果找到则返回 `true`，否则返回 `false`。
*   二分搜索，O(log N) 复杂度。

### `std::lower_bound` / `std::upper_bound`

*   `lower_bound`：返回指向已排序范围中第一个不小于 (即大于或等于) 给定值的元素的迭代器。
*   `upper_bound`：返回指向已排序范围中第一个大于给定值的元素的迭代器。

## 修改算法

修改算法会更改范围内的元素。

### `std::copy`

*   将元素从一个范围复制到另一个范围。

<UniversalEditor title="复制比较" compare={true}>
```javascript !! js
// JavaScript: Array.prototype.slice(), 展开运算符
let source = [1, 2, 3];
let destination = [...source]; // 使用展开复制
console.log(destination); // [1, 2, 3]

let part = source.slice(0, 2); // 复制一部分
console.log(part); // [1, 2]
```

```cpp !! cpp
// C++: std::copy
#include <iostream>
#include <vector>
#include <algorithm> // For std::copy

int main() {
  std::vector<int> source = {1, 2, 3};
  std::vector<int> destination(source.size()); // 预先分配空间
  std::copy(source.begin(), source.end(), destination.begin());
  // for (int n : destination) { std::cout << n << " "; }
  // std::cout << std::endl; // 输出: 1 2 3

  std::vector<int> part(2);
  std::copy(source.begin(), source.begin() + 2, part.begin());
  // for (int n : part) { std::cout << n << " "; }
  // std::cout << std::endl; // 输出: 1 2

  return 0;
}
```
</UniversalEditor>

### `std::transform`

*   对范围中的每个元素应用函数，并将结果存储在另一个范围中。

<UniversalEditor title="转换比较" compare={true}>
```javascript !! js
// JavaScript: Array.prototype.map()
let numbers = [1, 2, 3];
let doubled = numbers.map(num => num * 2);
console.log(doubled); // [2, 4, 6]
```

```cpp !! cpp
// C++: std::transform
#include <iostream>
#include <vector>
#include <algorithm> // For std::transform

int main() {
  std::vector<int> numbers = {1, 2, 3};
  std::vector<int> doubled(numbers.size());

  std::transform(numbers.begin(), numbers.end(), doubled.begin(),
                 [](int num) { return num * 2; }); // Lambda 函数

  // for (int n : doubled) { std::cout << n << " "; }
  // std::cout << std::endl; // 输出: 2 4 6

  return 0;
}
```
</UniversalEditor>

### `std::replace`

*   将范围中特定值的所有出现替换为另一个值。

## 数值算法

数值算法位于 `<numeric>` 标头中。

### `std::accumulate`

*   计算范围中元素的总和，或累加应用二元运算。

<UniversalEditor title="累加比较" compare={true}>
```javascript !! js
// JavaScript: Array.prototype.reduce()
let numbers = [1, 2, 3, 4, 5];
let sum = numbers.reduce((acc, current) => acc + current, 0);
console.log(sum); // 15
```

```cpp !! cpp
// C++: std::accumulate
#include <iostream>
#include <vector>
#include <numeric> // For std::accumulate

int main() {
  std::vector<int> numbers = {1, 2, 3, 4, 5};
  int sum = std::accumulate(numbers.begin(), numbers.end(), 0); // 初始值 0
  // std::cout << "Sum: " << sum << std::endl; // 输出: 15

  return 0;
}
```
</UniversalEditor>

### `std::inner_product`

*   计算两个范围的内积 (对应元素乘积的总和)。

## 与 JavaScript 数组方法的比较

JavaScript 的 `Array.prototype` 提供了许多内置方法，这些方法提供了与 STL 算法类似的功能。但是，存在关键差异：

| 特性           | JavaScript 数组方法                 | C++ STL 算法                       |
| :---------------- | :--------------------------------------- | :--------------------------------------- |
| **泛型**    | 通过动态类型实现              | 通过模板和迭代器实现     |
| **类型安全**   | 运行时类型检查                    | 编译时类型检查               |
| **性能**   | 通常内部优化，但动态类型/GC 带来开销 | 高度优化，直接内存访问，编译时优化 |
| **灵活性**   | 仅限于数组 (和类似数组的对象) | 适用于任何提供迭代器的容器 |
| **错误处理**| 抛出运行时错误                    | 类型不匹配的编译时错误，无效迭代器的运行时错误 |

## 算法性能分析

STL 算法通常经过高度优化，并提供强大的性能保证。它们的复杂度通常以其操作范围中的元素数量 (N) 表示。

*   **O(N) (线性)：** `std::find`、`std::copy`、`std::transform`、`std::accumulate`。
*   **O(N log N) (对数线性)：** `std::sort`、`std::stable_sort`。
*   **O(log N) (对数)：** `std::binary_search` (在已排序范围上)。

了解这些复杂度有助于为给定任务选择最合适的算法，尤其是在性能关键的应用程序中。

---

### 练习题：
1.  解释 `std::sort` 和 `std::stable_sort` 之间的区别。何时会优先选择其中一个？
2.  C++ 中的 `std::transform` 与 JavaScript 的 `Array.prototype.map()` 如何比较？提供一个简单的示例，其中使用 `std::transform` 将向量中的每个元素加倍。
3.  讨论使用 STL 算法相较于在 C++ 中手动实现类似功能的优点。

### 项目构想：
*   创建一个 C++ 程序，从文件中读取数字列表，对其进行排序，移除重复项，然后计算其总和和平均值。使用适当的 STL 容器和算法 (`std::vector`、`std::sort`、`std::unique`、`std::accumulate`)。将其性能与手动实现的排序和求和版本进行比较。
